package sort;

import java.util.Arrays;

/**
 * 希尔排序
 * 
 * @author fix 1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。
 *         它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
 */
public class ShellSort {

	public static void main(String[] args) {

		int sz[] = { 1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,16 };
		int gap = 1;  // 增量,不断/2 最终是 1,0
		int len = sz.length;
		int temp, i, j;
		int n=0;
	    
		for (gap=len/2 ; gap > 0; gap = gap / 2) {
			for (i = gap; i < len; i++) {				
				for (j = i; j-gap>=0 && sz[j]<sz[j-gap]; j-=gap) {
					temp=sz[j - gap];
					sz[j - gap]= sz[j];
					sz[j]=temp;
					n++;
				}
			}
		}

		System.out.println(Arrays.toString(sz));
		System.out.println(n);
	}

}
